1. Technical Field
The present invention relates to data communication networking devices, more particularly, to an arbitration logic architecture used in storing data frames in memory.
2. Background Art
In computer networks, a plurality of network stations are interconnected via a communications medium. For example, Ethernet is a commonly used local area network scheme in which multiple stations are connected to a single shared serial data path. These stations often communicate with a switch located between the shared data path and the stations connected to that path Typically, the switch controls the communication of data packets on the network.
When all of the stations connected to the network are simultaneously operating, packet traffic on the shared serial path can be heavy. In order for the data to be properly transmitted, the switch must manage the storage of these data packets within memory. Typically, a free buffer queue stores free address pointers; these free pointers point to available address space in memory where data can be stored. In a complex system such as a multiport switch, the free buffer queue provides a mechanism to orderly manage the requests for free pointers by various logic within the switch. An arbitration logic utilizes a round robin algorithm to honor the requests that are of identical priority. One approach to providing this type of arbitration scheme is discussed below with respect to Tables 1 and 2.
For the purposes of explanation, it is assumed that a multiport switch has six ports for the receipt and transmission of data frames. These six ports have equal priority. Each port has queuing logic tat executes requests to the free buffer queue for a free pointer upon receipt of a data frame. As indicated previously, a free pointer points to available space within memory for storage of the received data frame. The data frame is stored in the memory until the switch makes the appropriate switching decisions for that data frame, and is thereafter transmitted. To monitor and track which port should be granted the request, the arbitration logic, typically, has to maintain the following information (shown below):
The first column, labeled Counter Value, represents the values of a counter that is maintained by the arbitration logic. This counter value is also referred to as the slot number. The counter in this case is a 3-bit counter, which is incremented whenever an acknowledgement is sent by the arbitration logic to the respective port. As an illustration, Table 1 represents the conditions in which the arbitration logic may grant an acknowledgement to request 1 (REQ_1) from port 1. If the counter value is 1, for example, REQ_1 is 1 and the request bits that correspond to the remaining ports 2-6 are in a xe2x80x9cDON""T CARExe2x80x9d state (denoted by xe2x80x9cXxe2x80x9d). The second condition, in which REQ_1 is honored, is when the counter value is 2 and all the other requests are 0. If the counter value equals 3, REQ_1 is 1 while REQ_2 is in a xe2x80x9cDON""T CARExe2x80x9d state and the remaining requests bits are 0. REQ_2 is in a xe2x80x9cDON""T CARExe2x80x9d state because the arbitration logic checks the request sequentially and then loops back; thus, the acknowledgement would be sent out based upon REQ_1 being set to 1, which precedes REQ_2. The other conditions (i.e., when the counter equals 4, 5, and 6) follow the same rationale.
This scheme provides port 1 the absolute right to be granted an acknowledgement when the counter value is 1, assuming port 1 has a request. However, port 1 will only be granted an acknowledgement when the counter value is 2 if each of the other ports does not have a request. When the counter value is 3, port 1 will be granted and acknowledgement if it has a request and ports 3-6 do not. In this case, port 1 has priority over port 2 so that a request by port 2 does not matter in making the decision to grant an acknowledgement to port 1. It is apparent that for the arbitration logic to issue an acknowledgement, all the conditions of Table 1 have to be captured for only a single acknowledgement. Table 2 illustrates the conditions that must be satisfied to instruct the arbitration logic to issue an acknowledgement to REQ_2 from port 2. The conditions for granting the remaining requests (i.e., REQ_3, REQ_4, REQ_5, and REQ_6) exhibit a similar scheme.
Because of the numerous permutations that must be processed with respect to each acknowledgement, the conventional arbitration logic is complex. That is, the number of gates (or gate counts) increases with logic complexity, resulting in suboptimal performance and increased die size.
There exists a need for a implementing a more efficient round-robin arbitration architecture. There is also a need for reducing complexity of the arbitration logic. There is yet another need to minimize the die size of the device.
These and other needs are met by the present invention, where an arbitration logic grants acknowledgements to a requesting port in a round robin scheme. The architecture of the arbitration logic comprises multiple cells that are cascaded. The cascaded cells output an acknowledgement signal in response to an inhibit signal and a request signal. A counter maintains the order of the round robin scheme and is incremented only when the arbitration logic grants an acknowledgement
According to one aspect of the invention, a multiport switch is configured for controlling communication of data frames. The multiport switch comprises a buffer queue, which stores free buffer pointers. The free buffer pointers point to addresses of available memory space within the memory. A plurality of ports receive and transmit the data frames. Each of the ports is configured to output a request signal to request one of the free buffer pointers from the buffer queue. An arbitration logic receives and arbitrates the request signals from the plurality of ports according to a round robin scheme. The arbitration logic comprises a plurality of cells that correspond to the plurality of ports. These cells are cascaded in a prescribed sequence. The cell with the highest priority is able to send an acknowledgement signal to a corresponding requesting port, assuming the cell has received a request signal from that port. This highest priority cell concurrently sends an inhibit signal to the other lower priority cells to prevent each of these cells from sending another acknowledgement signal. The priorities of the cells are based in part on the relative positions of the cells within the prescribed sequence. This arrangement reduces complexity of the arbitration logic.
Another aspect of the present invention provides a method for storing data frames in memory. The method includes outputting a plurality of request signals to request a free buffer pointer. A free buffer pointer indicates an address of available space within the memory. The plurality of request signals are synchronized. The method also includes arbitrating the request signals in a round robin scheme by utilizing a plurality of cells cascaded in a prescribed sequence. The step of arbitrating comprises selecting a cell based upon a counter value, and outputting an inhibit signal from the selected cell in response to a corresponding request signal. The inhibit signal inhibits the other cells in the prescribed sequence from asserting their respective acknowledgement signals. The step of arbitrating further includes selectively asserting by the selected cell a corresponding acknowledgement signal based upon the corresponding request signal and a received inhibit signal, incrementing the counter value in response to the asserted acknowledgement signal, and obtaining the free buffer pointer in response to the asserted acknowledgement signal. Under this arrangement, arbitration of the request signals is efficiently performed.
Additional advantages and novel features of the invention will be set forth in part in the description which follows, and in part may become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.